package ACWing.DataStructure.堆;
//839. 模拟堆

import java.util.Scanner;

/**
 * @author :chenjie
 * @date :Created 2022/12/29 17:43
 */
public class DummyReactor {
    static int[]h=new int[100010];
    static int size;
    static int[]hp=new int[100010];//存储的是这个元素在ph中对应的下标
    static int[]ph=new int[100010];//存储的是第i次输入的这个值在h中存在的下标
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        sc.nextLine();
        int m=0;
        while (n-->0){
            String s=sc.next();
            if("I".equals(s)){
                int x=sc.nextInt();
                size++;
                m++;
                ph[m]=size;
                hp[size]=m;
                h[size]=x;
                up(size);
            }
            if("PM".equals(s)){
                if(size==0){
                    continue;
                }
                System.out.println(h[1]);
                continue;
            }
            if("D".equals(s)){
                int x=sc.nextInt();
                int k=ph[x];
                swap(k,size);
                size--;
                up(k);
                down(k);

            }
            if("DM".equals(s)){
                swap(1, size);
                size--;
                down(1);
            }
            if("C".equals(s)){
                int y=sc.nextInt();
                int x=sc.nextInt();
                int k=ph[y];
                h[k]=x;
                up(k);
                down(k);

            }
            sc.nextLine();
        }


    }
    public static void down(int u){
        int t=u;
        if(u*2<=size&&h[u*2]<h[t]){
            t=u*2;
        }
        if(u*2+1<=size&&h[u*2+1]<h[t]){
            t=u*2+1;
        }
        if(u!=t){
            swap(u,t);
            down(t);
        }
    }
    public static void up(int u){
        while (u/2>0&&h[u/2]>h[u]){
            swap(u,u/2);
            u=u/2;
        }
    }
    public static void swap(int a,int b){
        int temp=ph[hp[a]];
        ph[hp[a]]=ph[hp[b]];
        ph[hp[b]]=temp;
        temp=hp[a];
        hp[a]=hp[b];
        hp[b]=temp;
        temp=h[a];
        h[a]=h[b];
        h[b]=temp;
    }
}
